// This file is part of Eigen, a lightweight C++ template library
// for linear algebra.
//
// Copyright (C) 2016 Dmitry Vyukov <dvyukov@google.com>
// Copyright (C) 2016 Benoit Steiner <benoit.steiner.goog@gmail.com>
//
// This Source Code Form is subject to the terms of the Mozilla
// Public License v. 2.0. If a copy of the MPL was not distributed
// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

#define EIGEN_USE_THREADS
#include "main.h"
#include <Eigen/CXX11/ThreadPool>
#include <cstdlib>

// Visual studio doesn't implement a rand_r() function since its
// implementation of rand() is already thread safe
int
rand_reentrant(unsigned int* s)
{
#ifdef EIGEN_COMP_MSVC_STRICT
	EIGEN_UNUSED_VARIABLE(s);
	return rand();
#else
	return rand_r(s);
#endif
}

void
test_basic_runqueue()
{
	RunQueue<int, 4> q;
	// Check empty state.
	VERIFY(q.Empty());
	VERIFY_IS_EQUAL(0u, q.Size());
	VERIFY_IS_EQUAL(0, q.PopFront());
	std::vector<int> stolen;
	VERIFY_IS_EQUAL(0u, q.PopBackHalf(&stolen));
	VERIFY_IS_EQUAL(0u, stolen.size());
	// Push one front, pop one front.
	VERIFY_IS_EQUAL(0, q.PushFront(1));
	VERIFY_IS_EQUAL(1u, q.Size());
	VERIFY_IS_EQUAL(1, q.PopFront());
	VERIFY_IS_EQUAL(0u, q.Size());
	// Push front to overflow.
	VERIFY_IS_EQUAL(0, q.PushFront(2));
	VERIFY_IS_EQUAL(1u, q.Size());
	VERIFY_IS_EQUAL(0, q.PushFront(3));
	VERIFY_IS_EQUAL(2u, q.Size());
	VERIFY_IS_EQUAL(0, q.PushFront(4));
	VERIFY_IS_EQUAL(3u, q.Size());
	VERIFY_IS_EQUAL(0, q.PushFront(5));
	VERIFY_IS_EQUAL(4u, q.Size());
	VERIFY_IS_EQUAL(6, q.PushFront(6));
	VERIFY_IS_EQUAL(4u, q.Size());
	VERIFY_IS_EQUAL(5, q.PopFront());
	VERIFY_IS_EQUAL(3u, q.Size());
	VERIFY_IS_EQUAL(4, q.PopFront());
	VERIFY_IS_EQUAL(2u, q.Size());
	VERIFY_IS_EQUAL(3, q.PopFront());
	VERIFY_IS_EQUAL(1u, q.Size());
	VERIFY_IS_EQUAL(2, q.PopFront());
	VERIFY_IS_EQUAL(0u, q.Size());
	VERIFY_IS_EQUAL(0, q.PopFront());
	// Push one back, pop one back.
	VERIFY_IS_EQUAL(0, q.PushBack(7));
	VERIFY_IS_EQUAL(1u, q.Size());
	VERIFY_IS_EQUAL(1u, q.PopBackHalf(&stolen));
	VERIFY_IS_EQUAL(1u, stolen.size());
	VERIFY_IS_EQUAL(7, stolen[0]);
	VERIFY_IS_EQUAL(0u, q.Size());
	stolen.clear();
	// Push back to overflow.
	VERIFY_IS_EQUAL(0, q.PushBack(8));
	VERIFY_IS_EQUAL(1u, q.Size());
	VERIFY_IS_EQUAL(0, q.PushBack(9));
	VERIFY_IS_EQUAL(2u, q.Size());
	VERIFY_IS_EQUAL(0, q.PushBack(10));
	VERIFY_IS_EQUAL(3u, q.Size());
	VERIFY_IS_EQUAL(0, q.PushBack(11));
	VERIFY_IS_EQUAL(4u, q.Size());
	VERIFY_IS_EQUAL(12, q.PushBack(12));
	VERIFY_IS_EQUAL(4u, q.Size());
	// Pop back in halves.
	VERIFY_IS_EQUAL(2u, q.PopBackHalf(&stolen));
	VERIFY_IS_EQUAL(2u, stolen.size());
	VERIFY_IS_EQUAL(10, stolen[0]);
	VERIFY_IS_EQUAL(11, stolen[1]);
	VERIFY_IS_EQUAL(2u, q.Size());
	stolen.clear();
	VERIFY_IS_EQUAL(1u, q.PopBackHalf(&stolen));
	VERIFY_IS_EQUAL(1u, stolen.size());
	VERIFY_IS_EQUAL(9, stolen[0]);
	VERIFY_IS_EQUAL(1u, q.Size());
	stolen.clear();
	VERIFY_IS_EQUAL(1u, q.PopBackHalf(&stolen));
	VERIFY_IS_EQUAL(1u, stolen.size());
	VERIFY_IS_EQUAL(8, stolen[0]);
	stolen.clear();
	VERIFY_IS_EQUAL(0u, q.PopBackHalf(&stolen));
	VERIFY_IS_EQUAL(0u, stolen.size());
	// Empty again.
	VERIFY(q.Empty());
	VERIFY_IS_EQUAL(0u, q.Size());
	VERIFY_IS_EQUAL(0, q.PushFront(1));
	VERIFY_IS_EQUAL(0, q.PushFront(2));
	VERIFY_IS_EQUAL(0, q.PushFront(3));
	VERIFY_IS_EQUAL(1, q.PopBack());
	VERIFY_IS_EQUAL(2, q.PopBack());
	VERIFY_IS_EQUAL(3, q.PopBack());
	VERIFY(q.Empty());
	VERIFY_IS_EQUAL(0u, q.Size());
}

// Empty tests that the queue is not claimed to be empty when is is in fact not.
// Emptiness property is crucial part of thread pool blocking scheme,
// so we go to great effort to ensure this property. We create a queue with
// 1 element and then push 1 element (either front or back at random) and pop
// 1 element (either front or back at random). So queue always contains at least
// 1 element, but otherwise changes chaotically. Another thread constantly tests
// that the queue is not claimed to be empty.
void
test_empty_runqueue()
{
	RunQueue<int, 4> q;
	q.PushFront(1);
	std::atomic<bool> done(false);
	std::thread mutator([&q, &done]() {
		unsigned rnd = 0;
		std::vector<int> stolen;
		for (int i = 0; i < 1 << 18; i++) {
			if (rand_reentrant(&rnd) % 2)
				VERIFY_IS_EQUAL(0, q.PushFront(1));
			else
				VERIFY_IS_EQUAL(0, q.PushBack(1));
			if (rand_reentrant(&rnd) % 2)
				VERIFY_IS_EQUAL(1, q.PopFront());
			else {
				for (;;) {
					if (q.PopBackHalf(&stolen) == 1) {
						stolen.clear();
						break;
					}
					VERIFY_IS_EQUAL(0u, stolen.size());
				}
			}
		}
		done = true;
	});
	while (!done) {
		VERIFY(!q.Empty());
		int size = q.Size();
		VERIFY_GE(size, 1);
		VERIFY_LE(size, 2);
	}
	VERIFY_IS_EQUAL(1, q.PopFront());
	mutator.join();
}

// Stress is a chaotic random test.
// One thread (owner) calls PushFront/PopFront, other threads call PushBack/
// PopBack. Ensure that we don't crash, deadlock, and all sanity checks pass.
void
test_stress_runqueue()
{
	static const int kEvents = 1 << 18;
	RunQueue<int, 8> q;
	std::atomic<int> total(0);
	std::vector<std::unique_ptr<std::thread>> threads;
	threads.emplace_back(new std::thread([&q, &total]() {
		int sum = 0;
		int pushed = 1;
		int popped = 1;
		while (pushed < kEvents || popped < kEvents) {
			if (pushed < kEvents) {
				if (q.PushFront(pushed) == 0) {
					sum += pushed;
					pushed++;
				}
			}
			if (popped < kEvents) {
				int v = q.PopFront();
				if (v != 0) {
					sum -= v;
					popped++;
				}
			}
		}
		total += sum;
	}));
	for (int i = 0; i < 2; i++) {
		threads.emplace_back(new std::thread([&q, &total]() {
			int sum = 0;
			for (int j = 1; j < kEvents; j++) {
				if (q.PushBack(j) == 0) {
					sum += j;
					continue;
				}
				EIGEN_THREAD_YIELD();
				j--;
			}
			total += sum;
		}));
		threads.emplace_back(new std::thread([&q, &total]() {
			int sum = 0;
			std::vector<int> stolen;
			for (int j = 1; j < kEvents;) {
				if (q.PopBackHalf(&stolen) == 0) {
					EIGEN_THREAD_YIELD();
					continue;
				}
				while (stolen.size() && j < kEvents) {
					int v = stolen.back();
					stolen.pop_back();
					VERIFY_IS_NOT_EQUAL(v, 0);
					sum += v;
					j++;
				}
			}
			while (stolen.size()) {
				int v = stolen.back();
				stolen.pop_back();
				VERIFY_IS_NOT_EQUAL(v, 0);
				while ((v = q.PushBack(v)) != 0)
					EIGEN_THREAD_YIELD();
			}
			total -= sum;
		}));
	}
	for (size_t i = 0; i < threads.size(); i++)
		threads[i]->join();
	VERIFY(q.Empty());
	VERIFY(total.load() == 0);
}

EIGEN_DECLARE_TEST(cxx11_runqueue)
{
	CALL_SUBTEST_1(test_basic_runqueue());
	CALL_SUBTEST_2(test_empty_runqueue());
	CALL_SUBTEST_3(test_stress_runqueue());
}
